package com.atguigui.leetcode1;

import java.util.HashMap;
import java.util.Map;

/**
 * 1590.使数组和能被 P 整除
 * Project: leetcode
 * Package: com.atguigui.leetcode1
 * Version: 1.0
 * <p>
 * Created by WJX on 2023/3/10 9:36
 */
public class P1590MakeSumDivisibleByP {
    public static void main(String[] args) {
        Solution solution = new P1590MakeSumDivisibleByP().new Solution();
        // TO TEST
    }

    class Solution {
        public int minSubarray(int[] nums, int p) {
            int x = 0;
            for (int num : nums) {
                x = (x + num) % p;
            }
            if (x == 0) {
                return 0;
            }

            Map<Integer, Integer> index = new HashMap<Integer, Integer>();
            int y = 0, res = nums.length;

            for (int i = 0; i < nums.length; i++) {
                index.put(y, i); // f[i] mod p = y，因此哈希表记录 y 对应的下标为 i
                y = (y + nums[i]) % p;
                if (index.containsKey((y - x + p) % p)) {
                    res = Math.min(res, i - index.get((y - x + p) % p) + 1);
                }
            }

            return res == nums.length ? -1 : res;
        }
    }
}
